package com.wxit.algorithm.practice;

/**
 * 递归实现二分法查找
 */
public class BinarySearch {


    public static int search(int[] arr, int target) {
       return f(arr, target, 0, arr.length - 1);
    }

    private static int f(int[] a, int target, int i, int j) {

        if (i > j) {
            return -1;
        }

        int m = (i + j) >>> 1;
        if (target < a[m]) {
            //要查找的数据在左半边
            return f(a, target, i, m -1);
        } else if (target > a[m]) {
            //要查找的数据在右半边
            return f(a, target, m + 1, j);
        } else {
            return m;
        }
    }
}
